[Leetcode单排] Letter Combinations of a Phone Number(N17)

dfs search bfs

字数统计: 508阅读时长: 2 min

 2019/07/26  Share

17.Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

每个号码对应3或4个数字，输入一组号码，打印所有可能出现的排列。这道题很明显有BFS和DFS两类做法。

解法一

当处理第n个数字时，实际上就是以n-1次的处理结果加上第n个数字对应的几个字符进行处理。

/**
 * BFS 多层loop
 */
public List<String> letterCombinations(String digits) {
    if (digits == null || digits.length() == 0) {
        return new ArrayList<>();
    }
    String digitArr[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    result.add("");
    for (int i = 0; i < digits.length(); i++) {
        List<String> temp = new ArrayList<>();
        for (String str : result) {
            for (char c : digitArr[digits.charAt(i) - '0'].toCharArray()) {
                temp.add(str + c);
            }
        }
        result = temp;
    }
    return result;
}

在答案中看到另一种BFS的做法，他是以一个Queue作为载体。这种做法很巧妙，但是在写 while 和 for 中条件时还是比较容易出错的。

/**
 * BFS 使用queue，易错点在于while条件以及for中数组的获取
 */
public List<String> letterCombinations2(String digits) {
    if (digits == null || digits.length() == 0) {
        return new ArrayList<>();
    }
    String digitArr[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    LinkedList<String> result = new LinkedList<>();
    result.add("");
    while (result.peek().length() != digits.length()) {
        String peek = result.remove();
        for (char c : digitArr[digits.charAt(peek.length()) - '0'].toCharArray()) {
            result.add(peek + c);
        }
    }
    return result;
}

解法二

在DFS中，表示当前结果的 String cur，在每次递归中都是一个新的String。一般在DFS的递归之后需要对表示当前结果的值进行回滚，而在这种场景下则不需要。

/**
 * DFS 递归
 */
public List<String> letterCombinations3(String digits) {
    if (digits == null || digits.length() == 0) {
        return new ArrayList<>();
    }
    String digitArr[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    dfs(digits, digitArr, 0, "", result);
    return result;
}

private void dfs(String digits, String[] digitArr, int i, String cur, List<String> result) {
    if (i == digits.length()) {
        result.add(cur);
        return;
    }
    for (char c : digitArr[digits.charAt(i) - '0'].toCharArray()) {
        dfs(digits, digitArr, i + 1, cur + c, result);
    }
}

Next Post

[Leetcode单排] Subsets (N78 N90)
Previous Post

[Leetcode单排] 组合系列 (N39 N40 N77 N216)

CATALOG

1. 17.Letter Combinations of a Phone Number
1. 1.1. 解法一
2. 1.2. 解法二

